package 希尔排序;

import java.util.Arrays;

public class ShellSort {
    public static int[] shellSort(int[] arr) {
        int n = arr.length;
        //对每组间隔为h的分组进行排序
        for (int h = n / 2; h > 0; h /= 2) {
            //对每个局部分组进行插入排序
            for (int i = h; i < n; i++) {
                //将arr[i]插入到所在分组的正确位置上
                insertI(arr, h, i);
            }
        }
        return arr;
    }

    private static void insertI(int[] arr, int h, int i) {
        int temp = arr[i];
        int k;
        for (k = i - h; k >= 0 && temp < arr[k]; k -= h) {
            arr[k + h] = arr[k];
        }
        arr[k + h] = temp;
        System.out.println("hello");
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(shellSort(new int[]{5, 3, 4, 7, 9, 1})));
    }
}
